package Sort;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author Liangyaoyun
 */
public class MergeSortPlus {
    public void mergeSort(int[] list) {
        if(list == null || list.length == 0) {
            return;
        }
        int[] tmp = new int[list.length];
        mergeSortInner(list, 0, list.length-1, tmp);
    }

    /**
     通过递归结构实现的归并排序算法
     list为待排序序列
     low为待排序序列中，当前进行归并排序区间的起点下标
     high为待排序序列中，当前进行归并排序区间的终点下标
     tmp为归并排序使用的与待排序序列等长的临时空间
     */
    private void mergeSortInner(int[] list, int low, int high, int[] tmp) {

        //递归出口：当前区间长度为1
        if(high == low) {
            return;
        }

        int middle = (low + high) / 2;  //计算中值下标

        //递归调用：以中值下标为轴，对左右两部分子区间分别进行归并排序
        mergeSortInner(list, low, middle, tmp);
        mergeSortInner(list, middle+1, high, tmp);

        //递归调用结束后，左右两部分子区间分别有序

        /*
         借助临时空间，实现对左右两半部分的有序序列合并操作
         合并结果存储于原始序列的对应区间范围中
         */

        //将左半部分拷贝到临时空间中
        for(int i = low; i <= middle; i++) {
            tmp[i] = list[i];
        }

        //将右半部分拷贝到临时空间中
        for(int i = middle+1; i <= high; i++) {
            tmp[i] = list[i];
        }

        //开始有序序列（区间）合并操作
        int left = low;  //遍历左半部分区间的下标变量
        int right = middle+1;  //遍历右半部分区间的下标变量
        int index = low;  //控制较小元素落在list结果区间位置的下标变量

        while(left <= middle && right <= high) {
            if(tmp[left] < tmp[right]) {
                list[index] = tmp[left];
                left++;
            } else {
                list[index] = tmp[right];
                right++;
            }
            index++;
        }

        //如果左半部分区间存在剩余元素
        while(left <= middle) {
            list[index++] = tmp[left++];
        }

        //如果右半部分区间存在剩余元素
        while(right <= high) {
            list[index++] = tmp[right++];
        }

    }

    public static void main(String[] args) {
        MergeSortPlus mergeSort=new MergeSortPlus();
        int[] nums=new int[]{1,3,2,3,1};
        mergeSort.mergeSort(nums);
        for (int i = 0; i < 5; i++) {
            System.out.println(nums[i]);
        }
    }
}
